/** 
 * This class implements various string distances that can be used on
 * various kind of strings.
 *
 * This includes:
 * - equality
 * - subStringDistance
 * - pSubStringDistance [not implemented yet]
 * - lowenhein (edit) distance
 * - n-gram distance [not implemented yet]
 *
 * @author J�r�me Euzenat
 * @version $Id: StringDistances.java,v 1.6 2005/06/21 15:44:02 euzenat Exp $ 
 */
package jwnl;

import java.util.*;

public class StringDistances {

    /*
     * subStringDistance
     * computes substring distance:
     * = 1 - (2 | length of longest common substring | / |s1|+|s2|)
     * return: 0 if both string are equal, 1 otherwise
     */
    @SuppressWarnings("empty-statement")
    public static double subStringDistance(String s1, String s2) {
        if (s1 == null || s2 == null) {
            //throw new IllegalArgumentException("Strings must not be null");
            return 1.;
        }

        int l1 = s1.length(); // length of s
        int l2 = s2.length(); // length of t

        if ((l1 == 0) && (l2 == 0)) {
            return 0.;
        }
        if ((l1 == 0) || (l2 == 0)) {
            return 1.;
        }

        //int max = Math.min( l1, l2 ); // the maximal length of a subs
        int best = 0; // the best subs length so far

        int i = 0; // iterates through s1
        int j = 0; // iterates through s2

        for (i = 0; (i < l1) && (l1 - i > best); i++) {
            j = 0;
            while (l2 - j > best) {
                int k = i;
                for (; (j < l2) && (s1.charAt(k) != s2.charAt(j)); j++);
                if (j != l2) {// we have found a starting point
                    for (j++, k ++; (j< l2) && (k < l1) && (s1.charAt(k) == s2.charAt(j)); j++, k++);
		    best = Math.max( best, k-i );
		}
	    }
	}
		return (1.0 - ((double) 2 * best / (double) (l1 + l2)));
    }

    /*
     * pSubStringDistance: find all the common substrings (up to length 3) sum
     * their size / s1+s2
     */
    public static int equalDistance(String s, String t) {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }
        if (s.equals(t)) {
            return 1;
        } else {
            return 0;
        }
    }

    // JE: 30/05/2005: this has not been tested
    @SuppressWarnings("empty-statement")
    public static int ngramDistance(String s, String t) {
        int n = 3; // tri-grams for the moment
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }
        int found = 0;
        for (int i = 0; i < s.length() - n; i++) {
            for (int j = 0; j < t.length() - n; j++) {
                int k = 0;
                for (; (k < n) && s.charAt(i + k) == t.charAt(j + k); k++);
                if (k == n) {
                    found++;
                }
            }
        }
        return found;
    }

    /*
     * Pointer was provided in Todd Hugues (Lockheed) Taken from
     * http://www.merriampark.com/ldjava.htm Initial algorithm by Michael
     * Gilleland Integrated in Apache Jakarta Commons Improved by Chas Emerick
     * This algorithm should be taken appart of this file and reset in the
     * context of a proper package name with an acceptable license terms.
     * Hopefully, Jakarta Commons will provide this.
     */
    public static int levenshteinDistance(String s, String t) {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }

        /*
         * The difference between this impl. and the previous is that, rather
         * than creating and retaining a matrix of size s.length()+1 by
         * t.length()+1, we maintain two single-dimensional arrays of length
         * s.length()+1. The first, d, is the 'current working' distance array
         * that maintains the newest distance cost counts as we iterate through
         * the characters of String s. Each time we increment the index of
         * String t we are comparing, d is copied to p, the second int[]. Doing
         * so allows us to retain the previous cost counts as required by the
         * algorithm (taking the minimum of the cost count to the left, up one,
         * and diagonally up and to the left of the current cost count being
         * calculated). (Note that the arrays aren't really copied anymore, just
         * switched... this is clearly much better than cloning an array or
         * doing a System.arraycopy() each time through the outer loop.)
         *
         * Effectively, the difference between the two implementations is this
         * one does not cause an out of memory condition when calculating the LD
         * over two very large strings.
         */

        int n = s.length(); // length of s
        int m = t.length(); // length of t

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        int p[] = new int[n + 1]; // 'previous' cost array, horizontally
        int d[] = new int[n + 1]; // cost array, horizontally
        int _d[]; // placeholder to assist in swapping p and d

        // indexes into strings s and t
        int i; // iterates through s
        int j; // iterates through t

        char t_j; // jth character of t

        int cost; // cost

        for (i = 0; i <= n; i++) {
            p[i] = i;
        }

        for (j = 1; j <= m; j++) {
            t_j = t.charAt(j - 1);
            d[0] = j;

            for (i = 1; i <= n; i++) {
                cost = s.charAt(i - 1) == t_j ? 0 : 1;
                // minimum of cell to the left+1, to the top+1,
                // diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }

            // copy current distance counts to 'previous row' distance counts
            _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now
        // actually has the most recent cost counts
        // System.err.println(s+" x "+t+" = "+p[n]);
        return p[n];
    }

    static int min(int a, int b) {
        if (a < b) {
            return a;
        }
        return b;
    }

    static int max(int a, int b) {
        if (a > b) {
            return a;
        }
        return b;
    }

    static int prefixe(String str1, String str2) {
        int i;
        for (i = 0; i < min(str1.length(), str2.length()); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                return (i);
            }
        }
        return (i);
    }

    static float jarow(String str1, String str2) {
        int len1, len2, i, j, f1[], f2[], p, res = 0, tr = 0;
        float j1, j2;
        StringBuffer st1 = new StringBuffer(str1);
        StringBuffer st2 = new StringBuffer(str2);
        len1 = str1.length();
        len2 = str2.length();
        f1 = new int[len1];
        f2 = new int[len2];
        for (i = 0; i < len1; i++) {
            f1[i] = 0;
        }
        for (j = 0; j < len2; j++) {
            f2[j] = 0;
        }
        p = len2 / 2 - 1;
        for (i = 0; i < len1; i++) {
            for (j = max(i - p, 0); j < min(i + p + 1, len2); j++) {
                if (str1.charAt(i) == str2.charAt(j) && f2[j] == 0) {
                    res++;
                    f2[j] = 1;
                    f1[i] = 1;
                    break;
                }
            }
        }
        System.out.println("Carateres Commun: " + res);
        for (i = len1 - 1; i >= 0; i--) {
            if (f1[i] == 0) {
                st1.deleteCharAt(i);
            }
        }
        for (i = len2 - 1; i >= 0; i--) {
            if (f2[i] == 0) {
                st2.deleteCharAt(i);
            }
        }
        for (i = 0; i < st1.length(); i++) {
            if (st1.charAt(i) != st2.charAt(i)) {
                tr++;
            }
        }
        tr = tr / 2;
        System.out.println("Carateres transpose: " + tr);
        i = prefixe(str1, str2);
        System.out.println("Carateres prefixe: " + i);
        if (res == 0) {
            j1 = 0;
            j2 = 0;
        } else {
            j1 = (float) (1.0 / 3.0 * ((float) (res - tr) / res + (float) res / len1 + (float) res / len2));
            i = min(4, i);
            j2 = (float) ((i / 10.0) * (1.0 - j1));
        }
        j2 = j1 + j2;
        System.out.println("Jaro: " + j1 + "  jaro-winkler: " + j2);
        return (j2);
    }

    static int mongelkan(String str1, String str2) {

        float m = 0, max = 0, res = 0;
        int i1, i2, i, j;
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        StringTokenizer st1 = new StringTokenizer(str1, " ,;.!?:<>-=+*%�_/&#~([|@)]$�");
        StringTokenizer st2 = new StringTokenizer(str2, " ,;.!?:<>-=+*%�_/&#~([|@)]$�");
        Vector v1 = new Vector();
        Vector v2 = new Vector();
        i1 = 0;
        i2 = 0;
        while (st1.hasMoreTokens()) {
            v1.addElement(st1.nextToken());
            i1++;
        }
        while (st2.hasMoreTokens()) {
            v2.addElement(st2.nextToken());
            i2++;
        }
        for (i = v1.size() - 1; i >= 0; i--) {
            if (v1.elementAt(i).equals("un") || v1.elementAt(i).equals("une") || v1.elementAt(i).equals("le") || v1.elementAt(i).equals("la") || v1.elementAt(i).equals("les") || v1.elementAt(i).equals("de") || v1.elementAt(i).equals("des") || v1.elementAt(i).equals("est") || v1.elementAt(i).equals("ou") || v1.elementAt(i).equals("et") || v1.elementAt(i).equals("a") || v1.elementAt(i).equals("il")) {
                v1.remove(i);
            }
        }
        for (i = v2.size() - 1; i >= 0; i--) {
            if (v2.elementAt(i).equals("un") || v2.elementAt(i).equals("une") || v2.elementAt(i).equals("le") || v2.elementAt(i).equals("la") || v2.elementAt(i).equals("les") || v2.elementAt(i).equals("de") || v2.elementAt(i).equals("des") || v2.elementAt(i).equals("est") || v2.elementAt(i).equals("ou") || v2.elementAt(i).equals("et") || v2.elementAt(i).equals("a") || v2.elementAt(i).equals("il")) {
                v1.remove(i);
            }
        }
        for (i = 0; i < v1.size(); i++) {
            max = 0;
            for (j = 0; j < v2.size(); j++) {
                m = jarow((String) v1.elementAt(i), (String) v2.elementAt(j));
                if (max < m) {
                    max = m;
                }
            }
            res += max;
        }
        m = (float) (res / v1.size());
        System.out.println("Similarite de MONGE-ELKAN: " + m);
        return 0;
    }

    /**
     * JE//: This is independent from WordNet and should go to StringDistances
     * JE//: This should return a BagOfWords
     * the new tokenizer
     * first looks for non-alphanumeric chars in the string
     * if any, they will be taken as the only delimiters
     * otherwise the standard naming convention will be assumed:
     * words start with a capital letter
     * substring of capital letters will be seen as a whole
     * if it is a suffix
     * otherwise the last letter will be taken as the new token
     * start
     *
     * Would be useful to parameterise with stop words as well
     */
    public static Vector<String> tokenize(String s) {
        String str1 = s;
        int sLength = s.length();
        Vector<String> vTokens = new Vector<String>();

        // 1. detect possible delimiters
        // starts on the first character of the string
        int tkStart = 0;
        int tkEnd = 0;

        // looks for the first delimiter
        // while (tkStart < sLength  && isAlpha (str1.charAt(tkStart))) {
        while (tkStart < sLength && isAlphaNum(str1.charAt(tkStart))) {
            tkStart++;
        }

        // if there is one then the tokens will be the
        // substrings between delimiters
        if (tkStart < sLength) {

            // reset start and look for the first token
            tkStart = 0;

            // ignore leading separators
            // while (tkStart < sLength && ! isAlpha (str1.charAt(tkStart))) {
            while (tkStart < sLength && !isAlphaNum(str1.charAt(tkStart))) {
                tkStart++;
            }

            tkEnd = tkStart;

            while (tkStart < sLength) {

                // consumption of the Alpha/Num token
                if (isAlpha(str1.charAt(tkEnd))) {
                    while (tkEnd < sLength && isAlpha(str1.charAt(tkEnd))) {
                        tkEnd++;
                    }
                } else {
                    while (tkEnd < sLength && isNum(str1.charAt(tkEnd))) {
                        tkEnd++;
                    }
                }

                // consumption of the Num token
                vTokens.add(str1.substring(tkStart, tkEnd));

                // ignoring intermediate delimiters
                while (tkEnd < sLength && !isAlphaNum(str1.charAt(tkEnd))) {
                    tkEnd++;
                }
                tkStart = tkEnd;
            }
        } else { // else the standard naming convention will be used
            // start at the beginning of the string
            tkStart = 0;
            tkEnd = tkStart;

            while (tkStart < sLength) {

                // the beginning of a token
                if (isAlpha(str1.charAt(tkEnd))) {

                    if (isAlphaCap(str1.charAt(tkEnd))) {

                        // This starts with a Cap
                        // IS THIS an Abbreviaton ???
                        // lets see how maqny Caps
                        while (tkEnd < sLength && isAlphaCap(str1.charAt(tkEnd))) {
                            tkEnd++;
                        }

                        // The pointer is at:
                        // a) string end: make a token and go on
                        // b) number: make a token and go on
                        // c) a small letter:
                        // if there are at least 3 Caps,
                        // separate them up to the second last one and move the
                        // tkStart to tkEnd-1
                        // otherwise
                        // go on

                        if (tkEnd == sLength || isNum(str1.charAt(tkEnd))) {
                            vTokens.add(str1.substring(tkStart, tkEnd));
                            tkStart = tkEnd;
                        } else {
                            // small letter
                            if (tkEnd - tkStart > 2) {
                                // If at least 3
                                vTokens.add(str1.substring(tkStart, tkEnd - 1));
                                tkStart = tkEnd - 1;
                            }
                        }
                    // if (isAlphaSmall (str1.charAt(tkEnd))){}
                    } else {
                        // it is a small letter that follows a number : go on
                        // relaxed
                        while (tkEnd < sLength && isAlphaSmall(str1.charAt(tkEnd))) {
                            tkEnd++;
                        }
                        vTokens.add(str1.substring(tkStart, tkEnd));
                        tkStart = tkEnd;
                    }
                } else {
                    // Here is the numerical token processing
                    while (tkEnd < sLength && isNum(str1.charAt(tkEnd))) {
                        tkEnd++;
                    }
                    vTokens.add(str1.substring(tkStart, tkEnd));
                    tkStart = tkEnd;
                }
            }
        }
        // PV: Debug
        //System.err.println("Tokens = "+ vTokens.toString());
        return vTokens;
    }

    public static boolean isAlphaNum(char c) {
        return isAlpha(c) || isNum(c);
    }

    public static boolean isAlpha(char c) {
        return isAlphaCap(c) || isAlphaSmall(c);
    }

    public static boolean isAlphaCap(char c) {
        return (c >= 'A') && (c <= 'Z');
    }

    public static boolean isAlphaSmall(char c) {
        return (c >= 'a') && (c <= 'z');
    }

    public static boolean isNum(char c) {
        return (c >= '0') && (c <= '9');
    }
}
